1. Field of the Invention
The present invention relates generally to computer generated graphics, and more particularly, to clipping line segments against arbitrarily shaped polygons.
2. Related Art
Clipping a line segment against a polygon is necessary in the field of computer graphics. Clipping is required when a line segment intersects a polygon in order to display both the line and the polygon. Clipping is required, for example, when a polygon is filled with a cross-hatch pattern. In this example, each line in the cross-hatch pattern comprises an independent line segment which must be clipped to the inside of the polygon.
Computer graphics routines display line segments using the end points. Accordingly, a line segment is defined by its end points as opposed to each individual pixel displaying the line segment. When a polygon is overlaid on the line segment, the line segment may be totally visible, totally covered, or partially covered. In the partially covered case where one end point is visible and one end point is covered by the polygon, clipping must be performed to determine a new end point to temporarily replace the covered end point. This new end point is determined as the intersection of the line segment with the polygon. The new end point, or intersection point, defines the transition between the visible line segment (i.e., the line segment between the visible end point and the intersection point) and the clipped line segment (i.e., the line segment between the intersection point and the covered end point). This allows a computer graphics routine to properly display a line segment between the visible end point and the intersection point.
FIG. 1A illustrates several examples of where clipping a line segment is necessary to properly display overlaid items. A display 18 is a computer graphics display capable of displaying computer graphics. Displayed on display 18 are a background window 120, a foreground window 130, a triangle 140 (actually shown as a trapezoid) displayed in foreground window 130, and a star 150, filled with a cross-hatch pattern 180. FIG. 1A highlights and is used to define, several aspects of clipping a line segment against a polygon.
Star 150 will be used to define several temps. FIG. 1B illustrates star 150 in an enlarged view. Star 150 is formed by ten line segments 151-160. Each line segment 151-160 has two end points (not numbered). A line segment 151 intersects a line segment 152 at one of the respective end points of each line segment. This intersection is defined as a vertex 162. The end points comprising vertex 162 are also referred to as being coincident. Star 150, or any polygon, is defined in terms of the location of its vertices. Star 150 has ten vertices 161-170 each located at coincident end points of two of line segments 151-160.
When defining star 150, the order of vertices 161-170 is important because a computer graphics routine connects the vertices in the order in which they are presented to form the polygon. The order of the vertices begins with a starting vertex, followed by a next vertex, which may be followed by several more next vertices until a last vertex. Each vertex sequentially defines the perimeter of star 150. For example, vertex 161 is arbitrarily chosen as a first vertex. A next vertex is chosen as vertex 162. Several more next vertices are chosen in order along the perimeter of star 150 as vertex 163, vertex 164, vertex 165, vertex 166, and so forth, until a last vertex is chosen as vertex 170.
A computer graphics routine typically draws a line segment between each vertex beginning at the first vertex to a next vertex (e.g., vertex 161 to vertex 162 forming line segment 151) and proceeding to each subsequent next vertex following the order of the vertices 162-170. After drawing a line segment to the last vertex (e.g., vertex 169 to vertex 170 forming line segment 159), the graphics routine draws a final line segment (e.g., line segment 160) between the last vertex and the first vertex (e.g., vertex 170 to vertex 161 forming line segment 160) to complete the perimeter of star 150.
A present vertex is defined as the current vertex of interest or the vertex presently being examined. Relative to the present vertex are several other vertices which are defined in terms of the present vertex. A vertex immediately prior to the present vertex is referred to as a prior vertex. For example vertex 161 is a prior index with respect to vertex 162. A vertex immediately after the present vertex is referred to as a next vertex. For example, vertex 162 is a next vertex with respect to vertex 161. With respect to the first vertex, the last vertex is the prior vertex. For example, vertex 170 is a prior vertex with respect to vertex 161. With respect to the last vertex, the first vertex is the next vertex. For example, vertex 161 is a next vertex with respect to vertex 170.
Star 150 is referred to as a concave polygon. Concave polygons are defined as having at least one interior angle greater than 180 degrees. For example, the angle between line segment 155 and line segment 156 when measured through the interior of star 150 is greater than 180 degrees. All other polygons are convex polygons having interior angles less than 180 degrees. For example, background window 120, foreground window 130, and triangle 140 are all convex polygons.
Determination of whether a polygon is convex or concave can be important. This is best introduced by example. A line segment can intersect a convex polygon at a maximum of two locations. In contrast, a line segment can intersect a concave polygon at two or more locations. Referring to FIG. 1A, for example, line segment 131 (shown as line segments 131A, 131B, and 131C) intersects star 150 at four different locations. Specifically, line segment 131 intersects line segment 156, line segment 157, line segment 158, and line segment 159. Thus, a clipping algorithm must be able to distinguish between convex and concave polygons, or be able to handle clipping regardless of the polygon's concavity.
Foreground window 130 is comprised of four line segments 131-134. Background window 120 is comprised of four line segments 121-124. Foreground window 130 is overlaid on top of background window 120. As a result, line segment 122 (shown as line segment 122A and 122B) of background window 120 must be clipped in order to properly display foreground window 130 because a portion of line segment 122 lies beneath foreground window 130. This particular clip is referred to as an exterior clip because line segment 122 is clipped against window 130 to obtain those segments that lie outside window 130 as defined by its edges.
Triangle 140 is comprised of three line segments 141-143. Triangle 140 is displayed inside foreground window 130. Both line segment 141 and line segment 143 are clipped against foreground window 130. The result is that triangle 140 appears as a trapezoid inside foreground window 130. This is referred to as an interior clip because line segment 141 and 143 are clipped against window 130 to obtain those segments that lie inside window 130 as defined by its edges.
Star 150 is displayed on top of both background window 120 and foreground window 130. Line segment 131 of foreground window 130 is clipped against star 150. As discussed above, star 150 is a concave polygon. Clipping line segment 131 against star 150 here results in three line segments shown as line segment 131A, line segment 131B, and line segment 131C. Line segment 131 enters and exits polygon 150 twice resulting in two non-visible segments.
Another example of where clipping is used is for polygon fills. Referring again to FIG. 1B, star 150 demonstrates a polygon fill. A polygon fill is a pattern applied to the interior of a polygon. Cross-hatch pattern 180 is a polygon fill. Cross-hatch pattern 180 is comprised of two sets of parallel line segments 180A and 180B offset in angle from one another. Other examples of fills include parallel line fills such as star 150 filled solely with one set of parallel line segments such as parallel line segments 180A or 180B. For polygon fills, each line segment comprising the pattern must be clipped to the interior of the polygon. This is one type of application where conventional clipping algorithms are used. Other examples include virtual reality graphics where objects appear to move in three dimensions.
Two special cases can arise during clipping. One involves a line segment intersecting a vertex of a polygon. The other, known as a colinear intersection, involves a line segment intersecting a polygon along a side of the polygon in such a manner that the line segment is on top of the side of the polygon. A clipping algorithm must be able to handle these special cases.
Conventional clipping algorithms are well known in the prior art. However, conventional clipping algorithms perform all mathematical operations using fixed point, or integer, arithmetic. This poses several problems for computationally intensive applications, such as virtual reality graphics systems, which use floating point numbers extensively. Floating point numbers are required in these types of applications to accurately display graphic images.
Thus, in order to use conventional clipping algorithms, these types of applications must convert line segment end points and polygon vertices stored as floating point numbers into integers resulting in a loss of accuracy. Furthermore, small floating point numbers must be scaled up prior to conversion and clipping, and then scaled back down to avoid severe loss of accuracy. Conversely, large floating point numbers must be scaled down prior to conversion and clipping, and then scaled back up to avoid overflow. For polygons represented with both large and small floating point numbers, loss of accuracy is unavoidable using clipping algorithms that perform mathematical operations using integer arithmetic. This loss of accuracy results in intersections where there are none, and no intersections where there should be.
Thus, what is needed is a method for performing the entire clipping algorithm in the floating point domain.